#include <cstdio>
#include <cstring>

char a[ 10001 ], b[ 1001 ];
int next[ 1001 ], f[ 10001 ][ 1001 ], pi[ 1001 ][ 26 ];

int min( int a, int b ) { return ( a < b ) ?a :b; }

void getnext( char *a )
{
    int i = 1, j = -1;
    next[ 0 ] = -1;
    while ( a[ i ] )
    {
        while ( j >= 0 && a[ j + 1 ] != a[ i ] ) j = next[ j ];
        if ( a[ j + 1 ] == a[ i ] ) j++;
        next[ i++ ] = j;
    }
}

void work( )
{
    int i, j, p, n = strlen( a ), m = strlen( b ), minn = 1000000;
    memset( f, 0x3f, sizeof( f ) );
    f[ 0 ][ 0 ] = 0;
    for ( i = 0; i < n; i++ )
    {
        for ( j = 0; j < m; j++ )
        {
            f[ i + 1 ][ pi[ j ][ a[ i ] - 'a' ] + 1 ] = min( f[ i ][ j ], f[ i + 1 ][ pi[ j ][ a[ i ] - 'a' ] + 1 ] );
            f[ i + 1 ][ j ] = min( f[ i + 1 ][ j ], f[ i ][ j ] + 1 );
        }
    }
    for ( i = 0; i < m; i++ )
        if ( minn > f[ n ][ i ] )
            minn = f[ n ][ i ];
    printf("%d\n", minn);
}

void init( )
{
    int i, j, p, l = strlen( b );
    memset( pi, 0, sizeof( pi ) );
    for ( i = 0; i < l; i++ )
        for ( j = 0; j < 26; j++ )
        {
            p = i - 1;
            while ( p >= 0 && b[ p + 1 ] != j + 'a' ) p = next[ p ];
            if ( b[ p + 1 ] == j + 'a' ) p++;
            pi[ i ][ j ] = p;
        }
}

int main( )
{
    int t;
    scanf("%d", &t);
    while ( t-- )
    {
        scanf("%s%s", a, b);
        getnext( b );
        init( );
        work( );
    }
    return 0;
}
